#include <stdio.h>
#include <stdlib.h>

// 定义链表节点
typedef int elementType;

typedef struct lnode
{
    elementType data;
    struct lnode *next;
} Node, *LinkList;

// 创建节点
Node *CreateNode(elementType value)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 创建链表
LinkList CreateList()
{
    LinkList List = (LinkList)malloc(sizeof(Node)); // 创建头节点
    List->next = NULL;

    Node *current = List; // 定义当前节点

    while (1)
    {
        elementType value; // 输入元素
        scanf("%d", &value);

        if (value == -1)
            return List;

        current->next = CreateNode(value);
        current = current->next;
    }
}

// 合并链表并创建新节点
LinkList IntersectLists(LinkList S1, LinkList S2)//Intersect--相交
{
    LinkList S3 = (LinkList)malloc(sizeof(Node)); // 创建合并链表S3
    S3->next = NULL;

    Node *current = S3; // 定义当前链表

    S1 = S1->next; // 跳过头节点
    S2 = S2->next;

    while (S1 && S2) // 找到交集并插入节点到S3
    {
        if (S1->data < S2->data)
        {
            S1 = S1->next; // S1 当前节点小，跳到下一个
        }
        else if (S1->data > S2->data)
        {
            S2 = S2->next; // S2 当前节点小，跳到下一个
        }
        else // 找到相等的节点
        {
            current->next = CreateNode(S1->data); // 创建新节点并链接
            current = current->next; // 移动到当前链表的下一个
            S1 = S1->next; // 移动到下一个节点
            S2 = S2->next;
        }
    }

    return S3; // 返回新链表
}

// 打印链表
void PrintList(LinkList List)
{
    Node *current = List->next; // 从首元节点开始

    if (!current)
    { // 链表为空
        printf("NULL\n");
        return;
    }

    while (current)
    {
        printf("%d", current->data);
        current = current->next; // 移动到下一个节点
        if (current)
        {
            printf(" ");
        }
    }

    printf("\n");
}

// 释放链表内存
void FreeList(LinkList List)
{
    Node *current = List; // 从头节点开始
    while (current)
    {
        Node *temp = current;
        current = current->next; // 移动到下一个节点
        free(temp);              // 释放当前节点
    }
}

int main()
{
    // 构造链表S1 S2
    LinkList S1 = CreateList();
    LinkList S2 = CreateList();

    // 构造交集链表S3
    LinkList S3 = IntersectLists(S1, S2);

    // 打印输出S3
    PrintList(S3);

    // 释放链表内存
    FreeList(S1);
    FreeList(S2);
    FreeList(S3);

    return 0;
}
